/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */

/*
 * DC3 sort algorithm from:
 * http://jsuffixarrays.googlecode.com/svn-history/r40/trunk/src/java/org/jsuffixarrays/Skew.java
 *
 * Copyright (c) 2009, jsuffixarrays
 * 
 All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:
 * Redistributions of source code must retain the above copyright
 notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright
 notice, this list of conditions and the following disclaimer in the
 documentation and/or other materials provided with the distribution.
 * Neither the name of the <organization> nor the
 names of its contributors may be used to endorse or promote products
 derived from this software without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package util.sorting;

import java.util.Arrays;
import util.sedgewick.Stopwatch;

/**
 * <p>
 * Straightforward reimplementation of the recursive algorithm given in: <tt>
 * J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction.
 * In Proc. 13th International Conference on Automata, Languages and
 * Programming, Springer, 2003
 * </tt>
 * <p>
 * This implementation is basically a translation of the C++ version given by
 * Juha Kärkkäinen and Peter Sanders.
 * <p>
 * The implementation of this algorithm makes some assumptions about the input.
 * See {@link #buildSuffixArray(int[], int, int)} for details.
 */
public final class SkewSort {

    /**
     * Lexicographic order for pairs.
     */
    private final static boolean leq(int a1, int a2, int b1, int b2) {
        return (a1 < b1 || (a1 == b1 && a2 <= b2));
    }

    /**
     * Lexicographic order for triples.
     */
    private final static boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
        return (a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3)));
    }

    /**
     * Stably sort indexes from src[0..n-1] to dst[0..n-1] with values in 0..K
     * from v. A constant offset of
     * <code>vi</code> is added to indexes from src.
     */
    private final static void radixPass(int[] src, int[] dst, int[] v, int vi,
            final int n, final int K, int start) {
        // counter array
        final int[] cnt = new int[K + 1];

        // count occurrences
        for (int i = 0; i < n; i++) {
            cnt[v[start + vi + src[i]]]++;
        }

        // exclusive prefix sums
        for (int i = 0, sum = 0; i <= K; i++) {
            final int t = cnt[i];
            cnt[i] = sum;
            sum += t;
        }

        // sort
        for (int i = 0; i < n; i++) {
            dst[cnt[v[start + vi + src[i]]]++] = src[i];
        }
    }

    /**
     * Find the suffix array SA of s[0..n-1] in {1..K}^n. require s[n] = s[n+1]
     * = s[n+2] = 0, n >= 2.
     */
    static final void suffixArray(int[] s, int[] SA, int n, int K, int start) {
        final int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;

        final int[] s12 = new int[n02 + 3];
        s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
        final int[] SA12 = new int[n02 + 3];
        SA12[n02] = SA12[n02 + 1] = SA12[n02 + 2] = 0;
        final int[] s0 = new int[n0];
        final int[] SA0 = new int[n0];

        /*
         * generate positions of mod 1 and mod 2 suffixes the "+(n0-n1)" adds a dummy mod
         * 1 suffix if n%3 == 1
         */
        for (int i = 0, j = 0; i < n + (n0 - n1); i++) {
            if ((i % 3) != 0) {
                s12[j++] = i;
            }
        }

        // lsb radix sort the mod 1 and mod 2 triples
        radixPass(s12, SA12, s, +2, n02, K, start);
        radixPass(SA12, s12, s, +1, n02, K, start);
        radixPass(s12, SA12, s, +0, n02, K, start);

        // find lexicographic names of triples
        int name = 0, c0 = -1, c1 = -1, c2 = -1;
        for (int i = 0; i < n02; i++) {
            if (s[start + SA12[i]] != c0 || s[start + SA12[i] + 1] != c1
                    || s[start + SA12[i] + 2] != c2) {
                name++;
                c0 = s[start + SA12[i]];
                c1 = s[start + SA12[i] + 1];
                c2 = s[start + SA12[i] + 2];
            }

            if ((SA12[i] % 3) == 1) {
                // left half
                s12[SA12[i] / 3] = name;
            } else {
                // right half
                s12[SA12[i] / 3 + n0] = name;
            }
        }

        // recurse if names are not yet unique
        if (name < n02) {
            suffixArray(s12, SA12, n02, name, start);
            // store unique names in s12 using the suffix array
            for (int i = 0; i < n02; i++) {
                s12[SA12[i]] = i + 1;
            }
        } else {
            // generate the suffix array of s12 directly
            for (int i = 0; i < n02; i++) {
                SA12[s12[i] - 1] = i;
            }
        }

        // stably sort the mod 0 suffixes from SA12 by their first character
        for (int i = 0, j = 0; i < n02; i++) {
            if (SA12[i] < n0) {
                s0[j++] = 3 * SA12[i];
            }
        }
        radixPass(s0, SA0, s, 0, n0, K, start);

        // merge sorted SA0 suffixes and sorted SA12 suffixes
        for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
            // pos of current offset 12 suffix
            final int i = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
            // pos of current offset 0 suffix
            final int j = SA0[p];

            if (SA12[t] < n0 ? leq(s[start + i], s12[SA12[t] + n0], s[start + j],
                    s12[j / 3]) : leq(s[start + i], s[start + i + 1], s12[SA12[t] - n0 + 1],
                    s[start + j], s[start + j + 1], s12[j / 3 + n0])) {
                // suffix from SA12 is smaller
                SA[k] = i;
                t++;
                if (t == n02) {
                    // done --- only SA0 suffixes left
                    for (k++; p < n0; p++, k++) {
                        SA[k] = SA0[p];
                    }
                }
            } else {
                SA[k] = j;
                p++;
                if (p == n0) {
                    // done --- only SA12 suffixes left
                    for (k++; t < n02; t++, k++) {
                        SA[k] = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
                    }
                }
            }
        }
    }

    /**
     * {@inheritDoc}
     * <p>
     * Additional constraints enforced by Karkkainen-Sanders algorithm:
     * <ul>
     * <li>non-negative (>0) symbols in the input (because of radix sort)</li>,
     * <li><code>input.length</code> &gt;=
     * <code>start + length + 3</code> (to simplify border cases)</li>
     * <li>length >= 2</li>
     * </ul>
     * <p>
     * If the input contains zero or negative values, or has no extra trailing
     * cells, adapters can be used in the following way:
     *
     * <pre>
     * return new {@link DensePositiveDecorator}( new
     * {@link ExtraTrailingCellsDecorator}( new {@link Skew}(), 3));
     * </pre>
     *
     * @see ExtraTrailingCellsDecorator
     * @see DensePositiveDecorator
     */
    public int[] buildSuffixArray(int[] input, int start, int length) {
        //(input != null, "input must not be null");
        //assertAlways(length >= 2, "input length must be >= 2");
        //assertAlways(input.length >= start + length + 3, "no extra space after input end");
        //assert Tools.allPositive(input, start, length);

        final int[] tail = new int[3];
        final int[] SA = new int[length + 3];
        final int alphabetSize = Tools.max(input, start, length);
        System.arraycopy(input, start + length, tail, 0, 3);
        Arrays.fill(input, start + length, start + length + 3, 0);
        suffixArray(input, SA, length, alphabetSize, start);
        System.arraycopy(tail, 0, input, start + length, 3);

        return SA;
    }

    public static void main(String[] args) {

        // By radix sort: 
        //Unsorted: 9-3-2-4-2-4-1-6-0-4-1-2-4-0-0-5-2-4-1-7-8-
        //Sorted: 0-13-8-14-10-6-18-11-4-16-2-1-12-9-5-17-3-15-7-19-20-

        // Skew sort wants three zeros.
        int[] unsorted = {9, 3, 2, 4, 2, 4, 1, 6, 0, 4, 1, 2, 4, 0, 0, 5, 2, 4, 1, 7, 8, 0, 0, 0};
        SkewSort sn = new SkewSort();
        int[] sorted = sn.buildSuffixArray(unsorted, 0, unsorted.length - 3);
        for (int i : sorted) {
            System.out.print(i + " ");
        }
        System.out.println();
        int[] sortedDalesFormat = new int[sorted.length - 3];
        sortedDalesFormat[0] = 0;
        for (int i = 0; i < sorted.length - 4; i++) {
            sortedDalesFormat[i + 1] = sorted[i];
        }
        for (int i : sortedDalesFormat) {
            System.out.print(i + " ");
        }

        // Sorted output should be:
        // int[] sorted = {0, 13, 8, 14, 10, 6, 18, 11, 4, 16, 2, 1, 12, 9, 5, 17, 3, 15, 7, 19, 20};
    }

    /**
     * DC3 / Skew algorithm
     *
     * @param unsorted
     * @return
     */
    public int[] skewSort(int[] unsorted) {


        System.out.println("Starting DC3/Skew Sort...");
//        for(int i = 0 ; i < unsorted.length; i++) {
//            System.out.println(unsorted[i]);
//        }
        Stopwatch swSkewSort = new Stopwatch();
        int[] sorted = buildSuffixArray(unsorted, 0, unsorted.length - 3);
        System.out.println("finished within " + swSkewSort.elapsedTime() + " seconds.");
        int[] sortedrval = new int[sorted.length - 3];
        sortedrval[0] = 0;
        //? correct alternative ? System.arraycopy(sorted, 0, sortedrval, 1, sorted.length - 4);
        for (int i = 0; i < sorted.length - 4; i++) {
            sortedrval[i + 1] = sorted[i];
        }
        return sortedrval;

    }
}
